<!DOCTYPE html>





<html lang="zh-CN">
<head>
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/sunpages/images/apple-touch-icon-next.png?v=7.4.0">
  <link rel="icon" type="image/png" sizes="32x32" href="/sunpages/images/favicon-32x32-next.png?v=7.4.0">
  <link rel="icon" type="image/png" sizes="16x16" href="/sunpages/images/favicon-16x16-next.png?v=7.4.0">
  <link rel="mask-icon" href="/sunpages/images/logo.svg?v=7.4.0" color="#222">

<link rel="stylesheet" href="/sunpages/css/main.css?v=7.4.0">


<link rel="stylesheet" href="/sunpages/lib/font-awesome/css/font-awesome.min.css?v=4.7.0">


<script id="hexo-configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/sunpages/',
    scheme: 'Pisces',
    version: '7.4.0',
    exturl: false,
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":false},
    copycode: {"enable":true,"show_result":false,"style":null},
    back2top: {"enable":true,"sidebar":false,"scrollpercent":true},
    bookmark: {"enable":false,"color":"#222","save":"auto"},
    fancybox: false,
    mediumzoom: false,
    lazyload: false,
    pangu: false,
    algolia: {
      appID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    },
    localsearch: {"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},
    path: 'search.xml',
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    translation: {
      copy_button: '复制',
      copy_success: '复制成功',
      copy_failure: '复制失败'
    },
    sidebarPadding: 40
  };
</script>

  <meta name="description" content="实验四 实验报告 孙汉武    16281047    16281047">
<meta property="og:type" content="article">
<meta property="og:title" content="页面置换算法实验">
<meta property="og:url" content="https://yuandaima1.gitee.io/sunpages/2019/04/05/lab4/index.html">
<meta property="og:site_name" content="SunPages">
<meta property="og:description" content="实验四 实验报告 孙汉武    16281047    16281047">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-123542.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-125913.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-131355.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-132453.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-134926.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-135121.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-143913.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-141851.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-142312.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-144704.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-154625.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-145440.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-160411.jpg">
<meta property="og:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-160610.jpg">
<meta property="article:published_time" content="2019-04-05T12:10:33.000Z">
<meta property="article:modified_time" content="2019-09-12T09:34:31.000Z">
<meta property="article:author" content="sunhanwu">
<meta property="article:tag" content="操作系统">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-123542.jpg">
  <link rel="canonical" href="https://yuandaima1.gitee.io/sunpages/2019/04/05/lab4/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome: false,
    isPost: true,
    isPage: false,
    isArchive: false
  };
</script>

  <title>页面置换算法实验 | SunPages</title>
  








  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .logo,
  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript><!-- hexo-inject:begin --><!-- hexo-inject:end -->

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><div class="container use-motion">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-meta">

    <div>
      <a href="/sunpages/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">SunPages</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
        <h1 class="site-subtitle" itemprop="description">屁话少说,放码过来！</h1>
      
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
      
      
      
        
        <li class="menu-item menu-item-home">
      
    

    <a href="/sunpages/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-about">
      
    

    <a href="/sunpages/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i> <br>关于</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-tags">
      
    

    <a href="/sunpages/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i> <br>标签</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-categories">
      
    

    <a href="/sunpages/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i> <br>分类</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-archives">
      
    

    <a href="/sunpages/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br>归档</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-photos">
      
    

    <a href="/sunpages/photo/" rel="section"><i class="menu-item-icon fa fa-fw fa-image"></i> <br>Photos</a>

  </li>
      <li class="menu-item menu-item-search">
        <a href="javascript:;" class="popup-trigger">
        
          <i class="menu-item-icon fa fa-search fa-fw"></i> <br>搜索</a>
      </li>
    
  </ul>

</nav>
  <div class="site-search">
    <div class="popup search-popup">
    <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input" id="search-input"></div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="algolia-results">
  <div id="algolia-stats"></div>
  <div id="algolia-hits"></div>
  <div id="algolia-pagination" class="algolia-pagination"></div>
</div>

  
</div>
<div class="search-pop-overlay"></div>

  </div>
</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

  <a href="https://github.com/sunhanwu" class="github-corner" title="Follow me on GitHub" aria-label="Follow me on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
            

          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
      <article itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block post">
    <link itemprop="mainEntityOfPage" href="https://yuandaima1.gitee.io/sunpages/sunpages/2019/04/05/lab4/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="sunhanwu">
      <meta itemprop="description" content="Talk is cheap, show me the code!">
      <meta itemprop="image" content="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-09-12-logo.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="SunPages">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">页面置换算法实验

          
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              
                
              

              <time title="创建时间：2019-04-05 20:10:33" itemprop="dateCreated datePublished" datetime="2019-04-05T20:10:33+08:00">2019-04-05</time>
            </span>
          
            

            
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2019-09-12 17:34:31" itemprop="dateModified" datetime="2019-09-12T17:34:31+08:00">2019-09-12</time>
              </span>
            
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/sunpages/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%AE%9E%E9%AA%8C/" itemprop="url" rel="index"><span itemprop="name">操作系统实验</span></a></span>

                
                
              
            </span>
          

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
        
      
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/sunpages/2019/04/05/lab4/#comments" itemprop="discussionUrl"><span class="post-comments-count valine-comment-count" data-xid="/sunpages/2019/04/05/lab4/" itemprop="commentCount"></span></a>
  </span>
  
  
          <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="fa fa-file-word-o"></i>
              </span>
              
                <span class="post-meta-item-text">本文字数：</span>
              
              <span>12k</span>
            </span>
          
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="fa fa-clock-o"></i>
              </span>
              
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              
              <span>11 分钟</span>
            </span>
          

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="实验四-实验报告"><a href="#实验四-实验报告" class="headerlink" title="实验四 实验报告"></a><center>实验四 实验报告</center></h1><blockquote>
<center>孙汉武    16281047    16281047</center>

</blockquote><a id="more"></a>
<p><a href="https://github.com/sunhanwu/16281047_OperatingSystemExperiment/tree/master/lab4" target="_blank" rel="noopener">实验源码链接:https://github.com/sunhanwu/16281047_OperatingSystemExperiment/tree/master/lab4</a></p>
<h2 id="一-概要设计"><a href="#一-概要设计" class="headerlink" title="一 概要设计"></a>一 概要设计</h2><blockquote>
<p>实验源码请参考test.h</p>
</blockquote>
<h3 id="1-1-模块说明"><a href="#1-1-模块说明" class="headerlink" title="1.1 模块说明"></a>1.1 模块说明</h3><p>$\qquad$本实验共包含测试模块在内一共有7个模块，其中五个模块是算法模块，分别实现最佳置换算法、先入先出算法、最久未使用算法、改进的Clock算法、PBA页面缓冲算法和主模块。详细的细节如下：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">模块</th>
<th style="text-align:center">文件</th>
<th style="text-align:center">说明</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">测试模块</td>
<td style="text-align:center">test.h</td>
<td style="text-align:center">包含页面帧结构体的定义、随机访问序列的生成等测试函数</td>
</tr>
<tr>
<td style="text-align:center">最佳置换算法模块</td>
<td style="text-align:center">Optimal.h</td>
<td style="text-align:center">包含最佳置换算法函数</td>
</tr>
<tr>
<td style="text-align:center">先入先出算法模块</td>
<td style="text-align:center">FIFO.h</td>
<td style="text-align:center">包含先入先出算法函数</td>
</tr>
<tr>
<td style="text-align:center">最久未使用算法模块</td>
<td style="text-align:center">LRU.h</td>
<td style="text-align:center">包含最久未使用算法函数</td>
</tr>
<tr>
<td style="text-align:center">改进Clock算法模块</td>
<td style="text-align:center">Clock.h</td>
<td style="text-align:center">包含改进的Clock算法函数</td>
</tr>
<tr>
<td style="text-align:center">PBA页面缓冲算法模块</td>
<td style="text-align:center">PBA.h</td>
<td style="text-align:center">包含页面缓冲算法函数</td>
</tr>
<tr>
<td style="text-align:center">主模块</td>
<td style="text-align:center">main.cpp</td>
<td style="text-align:center">主函数</td>
</tr>
</tbody>
</table>
</div>
<h3 id="1-2-接口说明"><a href="#1-2-接口说明" class="headerlink" title="1.2 接口说明"></a>1.2 接口说明</h3><p>$\qquad$1.1 中所说的的各个模块中，测试模块是一个最基本的模块，它包含最基本的页面帧结构体的定义和随机访问序列生成函数等基本数据结构和函数。而六个算法模块都会引用测试模块中的数据结构和随机访问序列生成函数。而在主函数中进行对各个算法模块的调用。下面图示了各个模块之间的关系：</p>
<div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-123542.jpg" width="600"></div>

<h3 id="1-3-数据结构说明"><a href="#1-3-数据结构说明" class="headerlink" title="1.3 数据结构说明"></a>1.3 数据结构说明</h3><p>$\qquad$在本实验定一个很重要的表示页面帧的结构体，其成员变量及其作用如下图所示：</p>
<ol>
<li>WorkItem(表示帧结构体)</li>
</ol>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">WorkItem</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">int</span> seq;</span><br><span class="line">    <span class="keyword">int</span> priority;</span><br><span class="line">    <span class="keyword">char</span> Used;</span><br><span class="line">    <span class="keyword">char</span> Modified;</span><br><span class="line">&#125;WorkItem;</span><br></pre></td></tr></table></figure>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">变量名</th>
<th style="text-align:center">作用</th>
<th style="text-align:center">变量名</th>
<th style="text-align:center">作用</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">seq</td>
<td style="text-align:center">访问的序列号</td>
<td style="text-align:center">priority</td>
<td style="text-align:center">优先级</td>
</tr>
<tr>
<td style="text-align:center">Used</td>
<td style="text-align:center">Clock中的使用位</td>
<td style="text-align:center">Modified</td>
<td style="text-align:center">Clock中的修改位</td>
</tr>
</tbody>
</table>
</div>
<ol>
<li>MemSchedule(表示内存分配调度结构体)</li>
</ol>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">MemSchedule</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    WorkItem* WorkSpace=<span class="literal">NULL</span>;</span><br><span class="line">    <span class="keyword">int</span> *VisitSeq=<span class="literal">NULL</span>;</span><br><span class="line">    <span class="keyword">int</span> N=<span class="number">64</span>;</span><br><span class="line">    <span class="keyword">int</span> p=<span class="number">0</span>;</span><br><span class="line">    <span class="comment">//工作集大小</span></span><br><span class="line">    <span class="keyword">int</span> e=<span class="number">5</span>;</span><br><span class="line">    <span class="keyword">int</span> m=<span class="number">1</span>;</span><br><span class="line">    <span class="comment">//定义访问序列长度o</span></span><br><span class="line">    <span class="keyword">int</span> length;</span><br><span class="line">    <span class="comment">//当前已使用物理块数</span></span><br><span class="line">    <span class="keyword">int</span> work_len=<span class="number">0</span>;</span><br><span class="line">    <span class="comment">//发生替换的物理块号</span></span><br><span class="line">    <span class="keyword">int</span> change=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">float</span> t,r;</span><br><span class="line"><span class="comment">//   队列长度</span></span><br><span class="line">    <span class="keyword">int</span> queue_free_len = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> queue_modified_len = <span class="number">0</span>;</span><br><span class="line">    WorkItem <span class="built_in">free</span>[<span class="number">2</span>];</span><br><span class="line">    WorkItem Modified[<span class="number">2</span>];</span><br><span class="line">&#125;MemSchedule;</span><br></pre></td></tr></table></figure>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">变量名</th>
<th style="text-align:center">作用</th>
<th style="text-align:center">变量名</th>
<th style="text-align:center">作用</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">WorkSpace</td>
<td style="text-align:center">工作区间结构体数组</td>
<td style="text-align:center">VisitSeq</td>
<td style="text-align:center">访问序列数组</td>
</tr>
<tr>
<td style="text-align:center">N</td>
<td style="text-align:center">虚拟内存大小</td>
<td style="text-align:center">p</td>
<td style="text-align:center">工作集起始位置</td>
</tr>
<tr>
<td style="text-align:center">e</td>
<td style="text-align:center">工作区间大小</td>
<td style="text-align:center">m</td>
<td style="text-align:center">工作区间移动效率</td>
</tr>
<tr>
<td style="text-align:center">length</td>
<td style="text-align:center">访问序列长度</td>
<td style="text-align:center">work_len</td>
<td style="text-align:center">工作集中使用长度</td>
</tr>
<tr>
<td style="text-align:center">chang</td>
<td style="text-align:center">上一次发生替换的物理块号</td>
<td style="text-align:center">t,r</td>
<td style="text-align:center">随机访问序列算法参数</td>
</tr>
<tr>
<td style="text-align:center">queue_free_len</td>
<td style="text-align:center">PBA中的空闲队列长度</td>
<td style="text-align:center">queue_modifie_len</td>
<td style="text-align:center">PBA中修改队列长度</td>
</tr>
<tr>
<td style="text-align:center">free</td>
<td style="text-align:center">PBA中的空闲队列</td>
<td style="text-align:center">Modified</td>
<td style="text-align:center">PBA中的修改队列</td>
</tr>
</tbody>
</table>
</div>
<h3 id="1-4-随机访问序列生成算法"><a href="#1-4-随机访问序列生成算法" class="headerlink" title="1.4 随机访问序列生成算法"></a>1.4 随机访问序列生成算法</h3><p>$\qquad$实验中需要使用到随机访问序列，所以生成一个好的随机访问序列能很好的测试出各个算法的性能。下面是本实验中的随机算法访问序列生成算法的源码</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">MemSchedule <span class="title">GeneVisitSeq</span><span class="params">(<span class="keyword">int</span> l)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    MemSchedule schedule1;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"是否设定调度算法参数(Y/N):"</span>);</span><br><span class="line">    <span class="keyword">char</span> flag;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">"%c"</span>,&amp;flag);</span><br><span class="line">    <span class="keyword">if</span> (flag==<span class="string">'Y'</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        schedule1=SetMemSchedule(schedule1);</span><br><span class="line">    &#125;</span><br><span class="line">	schedule1.t=rand()%<span class="number">1000</span>/<span class="number">1000.0</span>;</span><br><span class="line">    schedule1.VisitSeq=(<span class="keyword">int</span> *)<span class="built_in">malloc</span>(l*<span class="keyword">sizeof</span>(schedule1.m));</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"生成随机内存访问序列：\n"</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;l;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;schedule1.m;j++)</span><br><span class="line">        &#123;</span><br><span class="line">            schedule1.VisitSeq[i*schedule1.m+j] = rand()%schedule1.e+schedule1.p;</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">"%d "</span>,schedule1.VisitSeq[i*schedule1.m+j]);</span><br><span class="line">        &#125;</span><br><span class="line">        schedule1.r=rand()%<span class="number">1000</span>/<span class="number">1000.0</span>;</span><br><span class="line">        <span class="keyword">if</span>(schedule1.r&lt;schedule1.t)</span><br><span class="line">        &#123;</span><br><span class="line">            schedule1.p=(schedule1.p+<span class="number">1</span>)%schedule1.N;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"\n"</span>);</span><br><span class="line">    schedule1.length=l*schedule1.m;</span><br><span class="line">    schedule1.WorkSpace = (WorkItem *)<span class="built_in">malloc</span>(schedule1.e *<span class="keyword">sizeof</span>(WorkItem));</span><br><span class="line">    <span class="keyword">return</span> schedule1;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>下面是其流程图：</p>
<div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-125913.jpg" width="500"></div>

<p>其描述为：</p>
<ul>
<li>首先生成算法需要的N p e m t等基本参数</li>
<li>生成m个范围在p到p+e之间的随机数加入到序列中</li>
<li>生成随机小数r</li>
<li>比较t和r，如果t比r小；则取一个新的p值；否则p=p+1 mod N</li>
<li>如果需要继续加长访问序列，则返回第二部继续执行；否则结束</li>
</ul>
<h3 id="1-5-算法通用流程"><a href="#1-5-算法通用流程" class="headerlink" title="1.5 算法通用流程"></a>1.5 算法通用流程</h3><p>$\qquad$各个页面置换算法中，大部分流程是一致的，只是在选择要替换的页面的时候选择的算法不一样，下面是这些算法的通用流程，而每个算法选择替换页号的时候将在后面仔细解释。</p>
<div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-131355.jpg" width="600"></div>

<p>其描述为：</p>
<ul>
<li>在访问序列中取出下一个要访问的页号，序列为空的话结束。</li>
<li>查看分配的内存内存块中是否还有剩余空间，有的话进行第三步；没有进行第四步</li>
<li>查看要访问的页号在以装入内存中是否存在，存在的话直接去下一个要访问的页号，从第一步开始执行；不存在则将新的物理块装入内存</li>
<li>查看要访问的页号在以装入内存中是否存在，存在的话直接去下一个要访问的页号，从第二部开始执行；不存在则利用算法找到要替换的内存块号，并将其替换，返回第一步</li>
</ul>
<h2 id="二-最佳置换算法"><a href="#二-最佳置换算法" class="headerlink" title="二 最佳置换算法"></a>二 最佳置换算法</h2><blockquote>
<p>实验源码请参照github中Optimal.h</p>
</blockquote>
<ol>
<li>算法描述</li>
</ol>
<p>$\qquad$最佳置换算法是一个理想的算法，其选择淘汰的页面是以后用不使用的，或者在将来最长时间用不使用的页面。采用最佳置换算法通常可以保证最低的缺页率。</p>
<ol>
<li><p>算法模拟</p>
<p> | 访问页面 | 4    | 4    | 3    | 5    | 6    | 3    | 6    | 7    | 9    | 7    | 10   | 9    | 11   | 12   |<br> | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |<br> | 内存块1  | 4    | 4    | 4    | 4    | 4    | 4    | 4    | 4    | 9    | 9    | 9    | 9    | 9    | 9    |<br> | 内存块2  |      |      | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 10   | 10   | 11   | 11   |<br> | 内存块3  |      |      |      | 5    | 5    | 5    | 5    | 5    | 5    | 5    | 5    | 5    | 5    | 12   |<br> | 内存块4  |      |      |      |      | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    |<br> | 内存块5  |      |      |      |      |      |      |      | 7    | 7    | 7    | 7    | 7    | 7    | 7    |</p>
<p> 上面是算法执行过程中页面的替换过程</p>
</li>
<li><p>算法实现</p>
<p> $\qquad$在概要设计中给出了各个算法的通用算法流程，但是各个算法在选择替换的内存块号的时候是不一致的。下面的是最佳置换算法中的实现。</p>
 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (flag == <span class="number">0</span>)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="comment">//min表示最小优先级的那个内存块号</span></span><br><span class="line">    <span class="keyword">int</span> min_pri=<span class="number">0xffffff</span>;</span><br><span class="line">    <span class="keyword">for</span> ( <span class="keyword">int</span> m=<span class="number">0</span>;m&lt;s1.work_len;m++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> n = SearchVisitSqe(s1.VisitSeq,i<span class="number">-1</span>,s1.WorkSpace[m].seq,<span class="number">0</span>,s1.length-s1.work_len+m);</span><br><span class="line">        s1.WorkSpace[m].priority = n;</span><br><span class="line">        <span class="keyword">if</span> (n &lt; min_pri)</span><br><span class="line">        &#123;</span><br><span class="line">            s1.change = m;</span><br><span class="line">            min_pri = n;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//表示发生替换变化的块号s1.change</span></span><br><span class="line">    s1.WorkSpace[s1.change].seq = pointer;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p> $\qquad$在这个代码片段中可以看到，通过<code>SearchVisitSeq</code>函数找到当前内存块中的页号下一次在访问序列中出现的距离，并将该距离最为优先级的值更新给每个内存块。最后判断哪个优先级小，说明那个物理块将来出现的时间越长，将替换它。</p>
</li>
<li><p>在主函数中调用最佳置换算法函数，会得到如下结果：</p>
</li>
</ol>
<div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-132453.jpg" width="600"></div>

<blockquote>
<p>带有@符号的表示这是新替换的页面，带有@的一行说明发生了缺页</p>
</blockquote>
<ol>
<li>算法性能评价</li>
</ol>
<p>$\qquad$程序设计中给出了两个评价算法性能的指标，分别是缺页率，下面将会给出在不同的虚拟内存和工作集的情况下两个指标的变化情况。</p>
<p>$\qquad$由于时间开销在算法中无法模拟，只能通过了理论的分析得到。下面只给出缺页率与工作集大小和虚拟内训大小之间的关系。</p>
<p>​    工作集大小与缺页率之间的关系：</p>
<div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-134926.jpg" width="400"></div>

<p>$\qquad$对应的曲线为：</p>
<div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-135121.jpg" width="400"></div> 

<p>$\qquad$对于这个曲线做出的解释如下：</p>
<ul>
<li>当工作集比较小的时候，频繁的发生缺页导致缺页率高</li>
<li>当工作集增大时，由于内存块数增多，减少页面的发生，缺页率减少。</li>
<li>当工作集再继续增大的时候，前面物理块空闲的时候页面装入也算做缺页，所以缺页率再次上升</li>
<li>当工作集大小达到一定程度的时候，缺页率会一直减小</li>
</ul>
<p>当工作集不变的时候，更改虚拟内存的时候分析缺页率的变化：</p>
<div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-143913.jpg" width="400"></div>

<p>其对应的曲线图为：</p>
<div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-141851.jpg" width="400"></div>

<h2 id="三-先入先出置换算法"><a href="#三-先入先出置换算法" class="headerlink" title="三  先入先出置换算法"></a>三  先入先出置换算法</h2><blockquote>
<p>实验源码请参考github中的FIFO.h</p>
</blockquote>
<ol>
<li><p>算法描述</p>
<p> 是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。 </p>
</li>
<li><p>算法模拟</p>
<p> | 访问页面 | 4    | 4    | 3    | 5    | 6    | 3    | 6    | 7    | 9    | 7    | 10   | 9    | 11   | 12   |<br> | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |<br> | 内存块1  | 4    | 4    | 4    | 4    | 4    | 4    | 4    | 4    | 9    | 9    | 9    | 9    | 9    | 9    |<br> | 内存块2  |      |      | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 11   | 11   |<br> | 内存块3  |      |      |      | 5    | 5    | 5    | 5    | 5    | 5    | 5    | 10   | 10   | 10   | 10   |<br> | 内存块4  |      |      |      |      | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 12   |<br> | 内存块5  |      |      |      |      |      |      |      | 7    | 7    | 7    | 7    | 7    | 7    | 7    |</p>
</li>
<li><p>算法实现</p>
<p> 在概要设计中给出了各个算法的通用算法流程，但是各个算法在选择替换的内存块号的时候是不一致的。下面的是先入先出置换算法中的实现。</p>
 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (flag == <span class="number">0</span>)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="comment">//min表示最小优先级的那个内存块号</span></span><br><span class="line">    <span class="keyword">int</span> min_pri=<span class="number">0xffffff</span>;</span><br><span class="line">    <span class="keyword">for</span> ( <span class="keyword">int</span> m=<span class="number">0</span>;m&lt;s1.work_len;m++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//和其他算法的区别只有优先级排序计算的方式不同</span></span><br><span class="line">        <span class="keyword">int</span> n = s1.WorkSpace[m].priority;</span><br><span class="line">        <span class="keyword">if</span> (n &lt; min_pri)</span><br><span class="line">        &#123;</span><br><span class="line">            s1.change = m;</span><br><span class="line">            min_pri = n;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//表示发生替换变化的块号s1.change</span></span><br><span class="line">    s1.WorkSpace[s1.change].seq = pointer;</span><br><span class="line">    <span class="comment">//设置新换入的页面优先级为work_len</span></span><br><span class="line">    s1.WorkSpace[s1.change].priority = s1.e;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p> $\qquad$在先入先出置换算法中每次新置换一个内存块将其优先级设置为工作区大小，之后每次运行一次，工作区中的所有内存块的优先级都减一，替换的时候找到优先级最小的替换就行了。</p>
</li>
<li><p>运行结果</p>
 <div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-142312.jpg" width="600"></div>

</li>
</ol>
<h2 id="四-最久未使用置换算法"><a href="#四-最久未使用置换算法" class="headerlink" title="四 最久未使用置换算法"></a>四 最久未使用置换算法</h2><blockquote>
<p>实验源码请参考github中的LRU.h文件</p>
</blockquote>
<ol>
<li><p>算法描述</p>
<p> 这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。</p>
</li>
<li><p>算法模拟</p>
<p> | 访问页面 | 4    | 4    | 3    | 5    | 6    | 3    | 6    | 7    | 9    | 7    | 10   | 9    | 11   | 12   |<br> | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |<br> | 内存块1  | 4    | 4    | 4    | 4    | 5    | 4    | 4    | 4    | 9    | 9    | 9    | 9    | 9    | 9    |<br> | 内存块2  |      |      | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 11   | 11   |<br> | 内存块3  |      |      |      | 5    | 5    | 5    | 5    | 5    | 5    | 5    | 10   | 10   | 10   | 10   |<br> | 内存块4  |      |      |      |      | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 12   |<br> | 内存块5  |      |      |      |      |      |      |      | 7    | 7    | 7    | 7    | 7    | 7    | 7    |</p>
</li>
<li><p>算法实现</p>
<p> 在概要设计中给出了各个算法的通用算法流程，但是各个算法在选择替换的内存块号的时候是不一致的。下面的是最久未使用置换算法中的实现。</p>
 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (flag == <span class="number">0</span>)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="comment">//min表示最小优先级的那个内存块号</span></span><br><span class="line">    <span class="keyword">int</span> min_pri=<span class="number">-10000</span>;</span><br><span class="line">    <span class="keyword">for</span> ( <span class="keyword">int</span> m=<span class="number">0</span>;m&lt;s1.work_len;m++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> n = SearchVisitSqe(s1.VisitSeq,i,s1.WorkSpace[m].seq,<span class="number">1</span>,i);</span><br><span class="line">        s1.WorkSpace[m].priority = n;</span><br><span class="line">        <span class="keyword">if</span> (n &gt; min_pri)</span><br><span class="line">        &#123;</span><br><span class="line">            s1.change = m;</span><br><span class="line">            min_pri = n;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//表示发生替换变化的块号s1.change</span></span><br><span class="line">    s1.WorkSpace[s1.change].seq = pointer;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p> $\qquad$在LRU算法中，使用函数<code>SearchVisitSeq</code>向访问序列中已经访问过的序列反向查找与当前页号相同的页号的距离，并将其最为优先级赋值给内存块，每次替换前更新所有的内存块的优先级；替换的时候找到优先级最大的进行替换。</p>
</li>
<li><p>运行结果</p>
 <div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-144704.jpg" width="600"></div>

</li>
</ol>
<h2 id="五-改进的Clock置换算法"><a href="#五-改进的Clock置换算法" class="headerlink" title="五 改进的Clock置换算法"></a>五 改进的Clock置换算法</h2><ol>
<li><p>算法描述</p>
<p> $\qquad$LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。</p>
<p> $\qquad$简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。</p>
<p> $\qquad$CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得CLOCK算法更加高效。在使用位的基础上再增加一个修改位，则得到改进型的CLOCK置换算法。这样，每一帧都处于以下四种情况之一：</p>
<ul>
<li><p>最近未被访问，也未被修改(u=0, m=0)</p>
</li>
<li><p>最近被访问，但未被修改(u=1, m=0)</p>
</li>
<li><p>最近未被访问，但被修改(u=0, m=1)</p>
</li>
<li><p>最近被访问，被修改(u=1, m=1)</p>
</li>
</ul>
</li>
</ol>
<pre><code>算法执行如下操作步骤：

+ 从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧(u=0, m=0)用于替换。

+ 如果第1)步失败，则重新扫描，查找(u=0, m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。

+ 如果第2)步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供替换的帧。
</code></pre><ol>
<li><p>算法模拟</p>
<p> | 访问页面 | 4    | 4    | 3    | 5    | 6    | 3    | 6    | 7    | 9    | 7    | 10   | 9    | 11   | 12   |<br> | ———— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— | —— |<br> | 内存块1  | 4    | 4    | 4    | 4    | 4    | 4    | 4    | 4    | 4    | 4    | 10   | 10   | 10   | 12   |<br> | 内存块2  |      |      | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 3    | 11   | 11   |<br> | 内存块3  |      |      |      | 5    | 5    | 5    | 5    | 5    | 9    | 9    | 9    | 9    | 9    | 9    |<br> | 内存块4  |      |      |      |      | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    | 6    |<br> | 内存块5  |      |      |      |      |      |      |      | 7    | 7    | 7    | 7    | 7    | 7    | 7    |</p>
</li>
<li><p>算法实现</p>
<p> 改进的Clock算法比前几个算法来讲比较复杂，下面是其核心的实现过程，</p>
 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (flag == <span class="number">0</span>)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="comment">//表示内存块中没有出现过</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> t=<span class="number">0</span>;t&lt;<span class="number">2</span>;t++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> flag = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> m=<span class="number">0</span>;m&lt;s1.work_len;m++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (s1.WorkSpace[m].Used ==<span class="string">'N'</span> &amp;&amp; s1.WorkSpace[m].Modified ==<span class="string">'N'</span>)</span><br><span class="line">            &#123;</span><br><span class="line">                s1.change =m;</span><br><span class="line">                flag =<span class="number">1</span>;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (flag == <span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> m=<span class="number">0</span>;m&lt;s1.work_len;m++)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span>(s1.WorkSpace[m].Used ==<span class="string">'N'</span> &amp;&amp; s1.WorkSpace[m].Modified ==<span class="string">'Y'</span>)</span><br><span class="line">                &#123;</span><br><span class="line">                    s1.change = m;</span><br><span class="line">                    flag = <span class="number">1</span>;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                s1.WorkSpace[m].Used = <span class="string">'N'</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(flag!=<span class="number">0</span>)</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    s1.WorkSpace[s1.change].seq = pointer;</span><br><span class="line">    s1.WorkSpace[s1.change].Used = <span class="string">'Y'</span>;</span><br><span class="line">    s1.WorkSpace[s1.change].Modified = <span class="string">'N'</span>;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p> 通过下面的流程图来解释该算法在选择替换物理块的时候的流程。</p>
 <div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-154625.jpg" width="600"></div>

<p> 算法描述：</p>
<ul>
<li>首先查找有没有(0，0)类型的页面，有的话替换该页面，没有的话进行第二步</li>
<li>查找有没有(0，1)类型的页面，有的话替换该页面，没有的话进行第三步</li>
<li>如果第一步第二步都没有找到的话就将所有页面的使用位都置为0然后重复第一步</li>
</ul>
</li>
<li><p>运行结果</p>
 <div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-145440.jpg" width="600"></div>

</li>
</ol>
<blockquote>
<p>运行结果中的的第一个’Y/N’表示使用位,第二个’Y/N’表示修改位，@表示是新置换的页面</p>
</blockquote>
<h2 id="六-页面缓冲算法PBA"><a href="#六-页面缓冲算法PBA" class="headerlink" title="六 页面缓冲算法PBA"></a>六 页面缓冲算法PBA</h2><blockquote>
<p>实验源码请参考github中的PBA.h</p>
</blockquote>
<ol>
<li><p>算法描述</p>
<p> $\qquad$严格意义上说PBA算法是一种页面缓冲算法，意义在于提高算法性能，减少从磁盘读取物理块到内存中的时间，提高算法的效率。而真正的页面置换算法采用的是前面所述的几种页面置换算法。本实验中采用的是FIFO置换算法。</p>
<p> $\qquad$在PBA算法中使用了两个队列，分别是使用空闲页面队列和修改页面队列。采用可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，而是依据是否修改分别挂到空闲页面链表或已修改页面链表的末尾</p>
<p> $\qquad$空闲页面链表同时用于物理块分配。当已修改页面链表达到一定长度如Z个页面时，一起将所有已修改页面写回磁盘，故可显著减少磁盘I/O操作次数</p>
</li>
<li><p>算法模拟</p>
 <div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-160411.jpg" width="600"></div>
</li>
<li><p>算法实现</p>
 <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (flag == <span class="number">0</span>)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="comment">//min表示最小优先级的那个内存块号</span></span><br><span class="line">    <span class="keyword">int</span> min_pri=<span class="number">0xffffff</span>;</span><br><span class="line">    <span class="keyword">for</span> ( <span class="keyword">int</span> m=<span class="number">0</span>;m&lt;s1.work_len;m++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//和其他算法的区别只有优先级排序计算的方式不同</span></span><br><span class="line">        <span class="keyword">int</span> n = s1.WorkSpace[m].priority;</span><br><span class="line">        <span class="keyword">if</span> (n &lt; min_pri)</span><br><span class="line">        &#123;</span><br><span class="line">            s1.change = m;</span><br><span class="line">            min_pri = n;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//表示发生替换变化的块号s1.change</span></span><br><span class="line">    s1.WorkSpace[s1.change].seq = pointer;</span><br><span class="line">    <span class="comment">//设置新换入的页面优先级为work_len</span></span><br><span class="line">    s1.WorkSpace[s1.change].priority = s1.e;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p> $\qquad$PBA 算法在页面置换的时候算法实现和FIFO一致。这里不再赘述</p>
</li>
<li><p>运行结果</p>
 <div align="center"><img src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-05-27-160610.jpg" width="600"></div>


</li>
</ol>

    </div>

    
    
    
        
      
        <div id="reward-container">
  <div></div>
  <button id="reward-button" disable="enable" onclick="var qr = document.getElementById(&quot;qr&quot;); qr.style.display = (qr.style.display === 'none') ? 'block' : 'none';">
    打赏
  </button>
  <div id="qr" style="display: none;">
        
      
      <div style="display: inline-block">
        <img src="https://ipic-picgo.oss-cn-beijing.aliyuncs.com/20200705000845.png" alt="sunhanwu 支付宝">
        <p>支付宝</p>
      </div>

  </div>
</div>

      

      <footer class="post-footer">
          
            
          
          <div class="post-tags">
            
              <a href="/sunpages/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" rel="tag"># 操作系统</a>
            
          </div>
        

        

          <div class="post-nav">
            <div class="post-nav-next post-nav-item">
              
                <a href="/sunpages/2019/04/02/pintos-install/" rel="next" title="pintos操作系统安装">
                  <i class="fa fa-chevron-left"></i> pintos操作系统安装
                </a>
              
            </div>

            <span class="post-nav-divider"></span>

            <div class="post-nav-prev post-nav-item">
              
                <a href="/sunpages/2019/04/06/2/" rel="prev" title="ryu控制器实现集线器">
                  ryu控制器实现集线器 <i class="fa fa-chevron-right"></i>
                </a>
              
            </div>
          </div>
        
      </footer>
    
  </div>
  
  
  
  </article>

  </div>


          </div>
          
    
    <div class="comments" id="comments"></div>
  

        </div>
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">
        
        
        
        
      

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#实验四-实验报告"><span class="nav-number">1.</span> <span class="nav-text">实验四 实验报告</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#一-概要设计"><span class="nav-number">1.1.</span> <span class="nav-text">一 概要设计</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#1-1-模块说明"><span class="nav-number">1.1.1.</span> <span class="nav-text">1.1 模块说明</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1-2-接口说明"><span class="nav-number">1.1.2.</span> <span class="nav-text">1.2 接口说明</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1-3-数据结构说明"><span class="nav-number">1.1.3.</span> <span class="nav-text">1.3 数据结构说明</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1-4-随机访问序列生成算法"><span class="nav-number">1.1.4.</span> <span class="nav-text">1.4 随机访问序列生成算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1-5-算法通用流程"><span class="nav-number">1.1.5.</span> <span class="nav-text">1.5 算法通用流程</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#二-最佳置换算法"><span class="nav-number">1.2.</span> <span class="nav-text">二 最佳置换算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#三-先入先出置换算法"><span class="nav-number">1.3.</span> <span class="nav-text">三  先入先出置换算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#四-最久未使用置换算法"><span class="nav-number">1.4.</span> <span class="nav-text">四 最久未使用置换算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#五-改进的Clock置换算法"><span class="nav-number">1.5.</span> <span class="nav-text">五 改进的Clock置换算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#六-页面缓冲算法PBA"><span class="nav-number">1.6.</span> <span class="nav-text">六 页面缓冲算法PBA</span></a></li></ol></li></ol></div>
        
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image"
      src="http://ipic-picgo.oss-cn-beijing.aliyuncs.com/2019-09-12-logo.jpg"
      alt="sunhanwu">
  <p class="site-author-name" itemprop="name">sunhanwu</p>
  <div class="site-description" itemprop="description">Talk is cheap, show me the code!</div>
</div>
  <nav class="site-state motion-element">
      <div class="site-state-item site-state-posts">
        
          <a href="/sunpages/archives/%20%7C%7C%20archive">
        
          <span class="site-state-item-count">29</span>
          <span class="site-state-item-name">博客</span>
        </a>
      </div>
    
      
      
      <div class="site-state-item site-state-categories">
        
          
            <a href="/sunpages/categories/%20%7C%7C%20th">
          
        
        <span class="site-state-item-count">7</span>
        <span class="site-state-item-name">分类</span>
        </a>
      </div>
    
      
      
      <div class="site-state-item site-state-tags">
        
          
            <a href="/sunpages/tags/%20%7C%7C%20tags">
          
        
        <span class="site-state-item-count">18</span>
        <span class="site-state-item-name">标签</span>
        </a>
      </div>
    
  </nav>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="https://github.com/sunhanwu" title="GitHub &rarr; https://github.com/sunhanwu" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="mailto:1965190613@qq.com" title="E-Mail &rarr; mailto:1965190613@qq.com" rel="noopener" target="_blank"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
      </span>
    
  </div>


  <div class="links-of-blogroll motion-element">
    <div class="links-of-blogroll-title">
      <i class="fa fa-fw fa-link"></i>
      Links
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="https://jackyanghc.github.io/" title="https://jackyanghc.github.io/" rel="noopener" target="_blank">Jackyanghc</a>
        </li>
      
        <li class="links-of-blogroll-item">
          <a href="https://michel-liu.github.io/" title="https://michel-liu.github.io/" rel="noopener" target="_blank">Michel</a>
        </li>
      
        <li class="links-of-blogroll-item">
          <a href="https://www.cnblogs.com/morwing/" title="https://www.cnblogs.com/morwing/" rel="noopener" target="_blank">morwing</a>
        </li>
      
    </ul>
  </div>

      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">sunhanwu</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
      <span class="post-meta-item-text">站点总字数：</span>
    
    <span title="站点总字数">161k</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
      <span class="post-meta-item-text">站点阅读时长 &asymp;</span>
    
    <span title="站点阅读时长">2:26</span>
</div>
  <div class="theme-info">主题 – <a href="https://theme-next.org" class="theme-link" rel="noopener" target="_blank">NexT.Pisces</a> v7.4.0</div>

        












        
      </div>
    </footer>
  </div>

  


  <script src="/sunpages/lib/anime.min.js?v=3.1.0"></script>
  <script src="/sunpages/lib/velocity/velocity.min.js?v=1.2.1"></script>
  <script src="/sunpages/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

<script src="/sunpages/js/utils.js?v=7.4.0.js"></script>

<script src="/sunpages/js/motion.js?v=7.4.0.js"></script>


<script src="/sunpages/js/schemes/pisces.js?v=7.4.0.js"></script>


<script src="/sunpages/js/next-boot.js?v=7.4.0.js"></script>




  
  <script>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>








  
<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/instantsearch.js@2/dist/instantsearch.min.css">
<script src="//cdn.jsdelivr.net/npm/instantsearch.js@2/dist/instantsearch.min.js"></script>
<script src="/sunpages/js/algolia-search.js?v=7.4.0.js"></script>
















  

  

  

  


<script>
NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
  var GUEST = ['nick', 'mail', 'link'];
  var guest = 'nick,mail,link';
  guest = guest.split(',').filter(item => {
    return GUEST.includes(item);
  });
  new Valine({
    el: '#comments',
    verify: false,
    notify: false,
    appId: 'ToSqcWxrMe4Fx1bTFKjHnFQn-gzGzoHsz',
    appKey: 'WIlMiWIudPsl2Q2PsMVfiUUH',
    placeholder: 'Just go go',
    avatar: 'mm',
    meta: guest,
    pageSize: '10' || 10,
    visitor: false,
    lang: '' || 'zh-cn',
    path: location.pathname
  });
}, window.Valine);
</script><!-- hexo-inject:begin --><!-- Begin: Injected MathJax -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config("");
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += ' has-jax';
    }
  });
</script>

<script type="text/javascript" src="">
</script>
<!-- End: Injected MathJax -->
<!-- hexo-inject:end -->

</body>
</html>
